package codetop.kuaishou.T1143;

/**
 * @Author: 18362
 * @Create: 2022-09-13 21:08:12 星期二
 */
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[] dp = new int[text2.length() + 1];
        for (int i = 0; i < text1.length(); i++) {
            int last = 0;
            for (int j=1; j<dp.length; ++j) {
                int t = dp[j];
                if (text1.charAt(i) == text2.charAt(j-1))
                    dp[j] = Math.max(last + 1, Math.max(dp[j], dp[j-1]));
                else
                    dp[j] = Math.max(dp[j], dp[j-1]);
                last = t;
            }
        }
        return dp[dp.length-1];
    }
}